package com.base.leetcode;

import com.sun.org.apache.regexp.internal.RE;

/**
 * @Author: hdhao
 * @Create: 2023/3/29 - 21:47
 * @Version: v1.0
 */
//反转链表测试
public class ListNodeTest {
    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
//        ListNode n1 = reverseList1(o1);
//        System.out.println(n1);
//        System.out.println("---------------------");
//        ListNode listNode = reverseList2(o1);
//        System.out.println(listNode);
        System.out.println("---------====------------");
//        ListNode listNode1 = reverseList3(o1);
//        System.out.println(listNode1);
//        ListNode listNode = reverseList4(o1);
//        System.out.println(listNode);
        ListNode listNode = reverseList5(o1);
        System.out.println(listNode);
    }
    //遍历旧的链表,将旧链表的节点中的值依次添加到新链表的头部
    public static ListNode reverseList1(ListNode o1){
        ListNode n1 = null;
        ListNode p = o1;
        while (p!=null){
            n1 = new ListNode(p.val,n1);
            p = p.next;
        }
        return n1;
    }

    static class LinkList{
        ListNode head;

        public LinkList(ListNode head){
            this.head = head;
        }
        //向头部添加
        public void addFirst(ListNode first){
            first.next = head;
            head = first;
        }
        //移除头结点
        public ListNode removeFirst(){
            ListNode first = head;
            if (first != null){
                head = first.next;
            }
            return first;
        }
    }
    //从旧链表头部移除节点,添加到新链表的头部,完成后的新链表既是倒序的
    public static ListNode reverseList2(ListNode head){
        LinkList list1 = new LinkList(head);
        LinkList list2 = new LinkList(null);
        while (true){
            ListNode first = list1.removeFirst();
            if (first == null){
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }
    //递归:先找链表的最后一个节点,将最后一个节点作为新链表的第一个节点
    public static ListNode reverseList3(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode last = reverseList3(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
    //从链表中每次拿到第二个节点,将其从链表断开,插入头部,直至它为null为止
    public static ListNode reverseList4(ListNode o1){
        if (o1 == null || o1.next == null){
            return o1;
        }
        //设置3个指针,o1(旧链表的头),o2(旧链表的第二个元素),n1(新链表的头)
        ListNode o2 = o1.next;
        ListNode n1 = o1;
        //当旧链表的第二个元素不是空的情况下就一直循环,说明链表中还有元素
        while (o2 != null){
            //断开旧链表中的第二个元素
            o1.next = o2.next;
            //将旧链表中的第二个元素添加到新链表的头部
            o2.next = n1;
            //更新n1的值(n1始终代表新链表的头)
            n1 = o2;
            //更新o2的值(o2始终代表旧链表的第二个元素)
            o2 = o1.next;
        }
        //返回新链表
        return n1;
    }
    //把链表分为两部分,思路是不断从旧链表的头往新链表的头移动
    public static ListNode reverseList5(ListNode o1){
        if (o1 == null || o1.next == null){
            return o1;
        }
        ListNode n1 = null;
        while (o1 != null){
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }

}
